#ifndef BTREE_H_INCLUDED
#define BTREE_H_INCLUDED
#include <stdio.h>

#endif // BTREE_H_INCLUDED

#define M 3                     // B树的阶，设为3
typedef int KeyType;            // 关键字类型

typedef enum Status{            // 表状态的枚举类
    SUCCESS,                    // 0-成功
    ERROR                       // 1-失败/错误
} Status;

/** B树的结点类型 **/
typedef struct BTNode{
    int keynum;                 // 关键字个数
    KeyType key[M+1];           // 关键字数组, key[0]未用
    struct BTNode *parent;      // 双亲结点指针
    struct BTNode *ptr[M+1];    // 孩子结点指针数组
    void *record[M+1];          // 记录指针向量，0号单元未用, 指向保存的数据
}BTNode, *BTree;                // B树的结点及指针类型

/** 返回的结果信息类型 **/
typedef struct result{
    BTree pt;                   // 指向找到的结点
    int i;                      // 在结点中的关键字位序(1 <= i <= m)
    int tag;                    // 1：查找成功 0：查找失败
}result, *resultptr;

/** 辅助打印索引结构类型 **/
typedef struct arr{
    int *thelast;               // 用于标记分隔符
    int max;                    // 最大值/层数
    int n;                      // 当前位/层
}arr, *array;

// 返回关键字k的位序
int search(BTree t, KeyType k);

// 分裂结点
void split(BTree t, int s, BTree *ap, void *rec);

// 创建新结点
void newRoot(BTree *p, BTree left, KeyType x, BTree right, void *rec);

// 插入
void insert(BTree t, int i, KeyType x, BTree p, void *rec);

// 找出Ai子树最下层非终端结点的最小关键字代替Ki
void successor(BTree *t, int i);

// 从结点中删除关键字key[i]
void removeKey(BTree t, int i);

// 调整BTree
void restore(BTree *root, BTree *t, int i);

// 为该位的索引结构添加标识并向下一层迁移
array append(array a, int last);

// 初始化一个array
array getArray();

// BTree的查找
resultptr searchBTree(BTree t, int k);

// 插入结点
Status insertBTree(BTree *t, KeyType k, BTree q, int i, void *rec);

// 删除结点
void deleteBTree(BTree *root, BTree *t, int i);

// 销毁BTree
Status destroyBTree(BTree t);

// 打印BTree索引结构
void printBTree(BTree t);

// 打印索引结构的功能函数
void print(BTree t, int depth, array last);

// 弹出当前位，回溯到上一层
array pop(array a);

// 初始化BTree结点
BTree getBTree();

// 初始化搜索结果信息
resultptr getResult(BTree t, int index, int tag);


